package sol.leetcode;

import def.ListNode;
import utils.LinkedListUtils;

/**
 * Reverse Linked List
 * Created by lkk on 2016/8/28.
 */
public class Issue206 {
    //循环
    public static ListNode reverseList(ListNode head) {
        ListNode ptr = head;
        ListNode newHead = null;
        while (ptr != null) {
            ListNode tmp = ptr;
            ptr = ptr.next;
            tmp.next = newHead;
            newHead = tmp;
        }
        return newHead;
    }

    //递归
    public static ListNode reverseList2(ListNode head) {
        return reverseHelper(null, head);
    }

    /**
     * @param newHead  已经转置的链表的头结点
     * @param leftHead 剩余待处理的头结点
     */
    public static ListNode reverseHelper(ListNode newHead, ListNode leftHead) {
        if (leftHead == null)
            return newHead;
        ListNode tmp = leftHead;
        leftHead = leftHead.next;
        tmp.next = newHead;
        newHead = tmp;
        return reverseHelper(newHead, leftHead);
    }

    public static void main(String[] args) {
        ListNode head = LinkedListUtils.create(1, 2, 3, 4, 5, 6);
        LinkedListUtils.print(head);

        LinkedListUtils.print(reverseList2(head));
    }
}
